package com.wonderplay.warlord.module.combat;


import java.util.ArrayList;
import java.util.List;

public class MainMatrix {

	public static final int EMPTY = -1;
	public static final int EMPTY_BY_HOR = -2;
	public static final int EMPTY_BY_VER = -3;
	public static final int EMPTY_BY_BOTH = -4;

	// The switch types
	public static final int SWITCH_INVALID = -1;
	public static final int SWITCH_LEFT = 0;
	public static final int SWITCH_RIGHT = 1;
	public static final int SWITCH_UP = 3;
	public static final int SWITCH_DOWN = 4;

	public static final int SEARCH_LEFT = 0;
	public static final int SEARCH_RIGHT = 1;
	public static final int SEARCH_UP = 3;
	public static final int SEARCH_DOWN = 4;
	public static final int SEARCH_HOR = 5;
	public static final int SEARCH_VER = 6;

	protected int width;
	protected int height;

	// main matrix to store unit type
	protected int[][] unitMatrix;

	// shadow matrix: a copy of main matrix before destory
	private int[][] shadowMatrix;

	// mask to judge if a unit can be destroyed, hor_num|ver_num
	private int[][] maskMatrix;

	public static final int HOR_VER_MASK = 1000;
	
	protected int eliminateNum = 3;

	protected int unitTypeNum = 5;

	List<EliminateCluster> eliminateClusterList;
	List<Suggestion> suggestionList;

	public MainMatrix(int width, int height, int eliminateNum, int unitTypeNum) {
		this.width = width;
		this.height = height;
		unitMatrix = new int[width][height];
		maskMatrix = new int[width][height];
		shadowMatrix = new int[width][height];
		eliminateClusterList = new ArrayList<EliminateCluster>();
		suggestionList = new ArrayList<Suggestion>();
		
		this.eliminateNum = eliminateNum;
		this.unitTypeNum = unitTypeNum;
	}

	public void initMaskMatrix() {
		for (int i = 0; i < width; i++) {
			for (int j = 0; j < height; j++)
				maskMatrix[i][j] = 0;
		}
	}

	public static int getMaskHorizontal(int maskNum) {
		return maskNum / HOR_VER_MASK;
	}

	public static int getMaskVertical(int maskNum) {
		return maskNum % HOR_VER_MASK;
	}

	public static boolean isEmpty(int unitNum) {
		return (unitNum < 0);
	}

	public static boolean isEmptyByHor(int unitNum) {
		return (unitNum == EMPTY_BY_HOR || unitNum == EMPTY_BY_BOTH);
	}

	public static boolean isEmptyByVer(int unitNum) {
		return (unitNum == EMPTY_BY_VER || unitNum == EMPTY_BY_BOTH);
	}

	public static int emptyByHor(int unitNum) {
		int returnValue = unitNum;
		if (unitNum >= 0) {
			returnValue = EMPTY_BY_HOR;
		} else if (unitNum != EMPTY_BY_HOR) {
			returnValue = EMPTY_BY_BOTH;
		}
		return returnValue;
	}

	public static int emptyByVer(int unitNum) {
		int returnValue = unitNum;
		if (unitNum >= 0) {
			returnValue = EMPTY_BY_VER;
		} else if (unitNum != EMPTY_BY_VER) {
			returnValue = EMPTY_BY_BOTH;
		}
		return returnValue;
	}

	public void generateMaskMatrix() {
		initMaskMatrix();

		// search from topLeft to bottomRight
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {

				// calculate horizontal
				if (x + 1 < width){
					if (unitMatrix[x][y] == unitMatrix[x + 1][y]) {
						maskMatrix[x + 1][y] += (getMaskHorizontal(maskMatrix[x][y]) + 1)
						* HOR_VER_MASK;
					}
				}

				// calculate vertical
				if (y + 1 < height){
					if (unitMatrix[x][y] == unitMatrix[x][y + 1]) {
						maskMatrix[x][y + 1] += getMaskVertical(maskMatrix[x][y]) + 1;
					}
				}
			}
		}
	}

	public void backupShadow() {
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				shadowMatrix[x][y] = unitMatrix[x][y];
			}
		}
	}

	private void destroyEliminableByMask() {
		backupShadow();

		eliminateClusterList.clear();

		// query the generated maskMatrix and set the destroyed to EMPTY

		for (int x = width - 1; x >= 0; x--) {
			for (int y = height - 1; y >= 0; y--) {
				if (!isEmptyByHor(unitMatrix[x][y])) {
					int horNum = getMaskHorizontal(maskMatrix[x][y]) + 1;
					if (horNum >= eliminateNum) {
						for (int i = 0; i < horNum; i++) {
							unitMatrix[x - i][y] = emptyByHor(unitMatrix[x - i][y]);
						}

						EliminateCluster cluster = new EliminateCluster(x
								- horNum + 1, y, EliminateCluster.TYPE_X,
								horNum, shadowMatrix[x][y]);
						eliminateClusterList.add(cluster);
					}
				}

				if (!isEmptyByVer(unitMatrix[x][y])) {
					int verNum = getMaskVertical(maskMatrix[x][y]) + 1;
					if (verNum >= eliminateNum) {
						for (int i = 0; i < verNum; i++) {
							unitMatrix[x][y - i] = emptyByVer(unitMatrix[x][y
									- i]);
						}

						EliminateCluster cluster = new EliminateCluster(x, y
								- verNum + 1, EliminateCluster.TYPE_Y, verNum,
								shadowMatrix[x][y]);
						eliminateClusterList.add(cluster);
					}
				}
			}
		}
	}

	public List<EliminateCluster> destroyEliminable() {
		generateMaskMatrix();
		destroyEliminableByMask();
		
		return eliminateClusterList;
	}

	private boolean hasDestroyableByMask() {
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				int mask = maskMatrix[x][y];
				if (getMaskHorizontal(mask) + 1 >= eliminateNum
						|| getMaskVertical(mask) + 1 >= eliminateNum) {
					return true;
				}
			}
		}
		return false;
	}

	public boolean hasDestroyable() {
		generateMaskMatrix();
		return hasDestroyableByMask();
	}

	private List<EliminateUnits> getEliminableByMask() {
		List<EliminateUnits> eliminateUnitsList = new ArrayList<EliminateUnits>();
		
		backupShadow();

		// query the generated maskMatrix and set the destroyed to EMPTY

		for (int x = width - 1; x >= 0; x--) {
			for (int y = height - 1; y >= 0; y--) {
				if (!isEmptyByHor(unitMatrix[x][y])) {
					int horNum = getMaskHorizontal(maskMatrix[x][y]) + 1;
					if (horNum >= eliminateNum) {
						EliminateUnits units = new EliminateUnits(shadowMatrix[x][y]);
						for (int i = 0; i < horNum; i++) {
							unitMatrix[x - i][y] = emptyByHor(unitMatrix[x - i][y]);
							
							units.add(new UnitPosition(x-i, y));
						}
						eliminateUnitsList.add(units);
					}
				}

				if (!isEmptyByVer(unitMatrix[x][y])) {
					int verNum = getMaskVertical(maskMatrix[x][y]) + 1;
					if (verNum >= eliminateNum) {
						EliminateUnits units = new EliminateUnits(shadowMatrix[x][y]);

						for (int i = 0; i < verNum; i++) {
							unitMatrix[x][y - i] = emptyByVer(unitMatrix[x][y
									- i]);
							units.add(new UnitPosition(x, y - i));
						}
						eliminateUnitsList.add(units);
					}
				}
			}
		}
		
		return eliminateUnitsList;
	}
	
	public List<EliminateUnits> getDestroyableUnitsList(){
		generateMaskMatrix();
		return getEliminableByMask();
	}
	
	// after move the matrix will become the following format, the empty units
	// will be moved to the top
	/**
	 * -1 2 -1 4 -1 1 3 6 3 3 5 1 1 1 3 2
	 */

	public void moveUnit() {
		for (int x = 0; x < width; x++) {
			int filledYPos = height - 1;
			for (int y = height - 1; y >= 0; y--) {
				if (isEmpty(unitMatrix[x][y])) {
					continue;
				} else {
					if (y != filledYPos) {
						unitMatrix[x][filledYPos] = unitMatrix[x][y];
						unitMatrix[x][y] = EMPTY;
					}
					filledYPos--;
				}
			}
		}
	}

	/**
	 * Needs change!
	 */
	public void fillEmptyUnits() {
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				if (isEmpty(unitMatrix[x][y])) {
					unitMatrix[x][y] = (int) ((unitTypeNum - 1) * Math.random() + 0.5);
				} else {
					break;
				}
			}
		}
	}

	private void fillRandomMatrix() {
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				unitMatrix[x][y] = (int) ((unitTypeNum - 1) * Math.random() + 0.5);
			}
		}
	}

	public void generateInitMatrix() {
		fillRandomMatrix();
		System.out.println(this.toString());

		generateMaskMatrix();
		System.out.println("mask");
		System.out.println(this.getMaskString());
		
		while (hasDestroyableByMask()) {
			destroyEliminableByMask();
			 System.out.println("des");
			 System.out.println(this.toString());

			moveUnit();
			 System.out.println("move");
			 System.out.println(this.toString());

			fillEmptyUnits();
			 System.out.println("fill");
			 System.out.println(this.toString());

			generateMaskMatrix();
			System.out.println("mask");
			System.out.println(this.getMaskString());
		}
	}

	public List<Suggestion> getAllSuggestions() {
		
		//TODO wrong function!!
		suggestionList.clear();

		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				// try to change for right side and down side then search for
				// four sides

				List<EliminateUnits> unitsList;
				// swith with the right unit
				if ((x + 1) < width && unitMatrix[x][y] != unitMatrix[x + 1][y]) {
					unitsList = searchForEliminate(x, y, SWITCH_RIGHT);
					
					if (unitsList != null && !unitsList.isEmpty()){
						suggestionList.add(new Suggestion(x, y, SWITCH_RIGHT));
					}
					
				}

				// swith with the down unit
				if ((y + 1) < height
						&& unitMatrix[x][y] != unitMatrix[x][y + 1]) {
					unitsList = searchForEliminate(x, y, SWITCH_DOWN);
					
					if (unitsList != null && !unitsList.isEmpty()){
						suggestionList.add(new Suggestion(x, y, SWITCH_DOWN));
					}
				}
			}
		}
		return suggestionList;
	}

	/**
	 * @param x
	 * @param y
	 * @param switchType
	 * @return
	 */
	public List<EliminateUnits> searchForEliminate(int x, int y, int switchType){
		List<EliminateUnits> units = new ArrayList<EliminateUnits>();
		
		EliminateUnits unitsPositive = null;
		EliminateUnits unitsNegative = null;
		
		switch(switchType){
		case SWITCH_RIGHT:
			if (x + 1 < width){
				unitsPositive = searchForEliminateSingleUnit(x, y, SWITCH_RIGHT);
				unitsNegative = searchForEliminateSingleUnit(x + 1, y, SWITCH_LEFT);
			}
			break;
		case SWITCH_LEFT:
			if (x - 1 >= 0){
				unitsPositive = searchForEliminateSingleUnit(x - 1, y, SWITCH_RIGHT);
				unitsNegative = searchForEliminateSingleUnit(x, y, SWITCH_LEFT);
			}
			break;
		case SWITCH_DOWN:
			if (y + 1 < height){
				unitsPositive = searchForEliminateSingleUnit(x, y, SWITCH_DOWN);
				unitsNegative = searchForEliminateSingleUnit(x, y + 1, SWITCH_UP);
			}
			break;
		case SWITCH_UP:
			if (y - 1 >= 0){
				unitsPositive = searchForEliminateSingleUnit(x, y - 1, SWITCH_DOWN);
				unitsNegative = searchForEliminateSingleUnit(x, y, SWITCH_UP);
			}
			break;
		default:
			break;
		}
		
		if (unitsPositive != null && !unitsPositive.isEmpty()){
			units.add(unitsPositive);
		}
		
		if (unitsNegative != null && !unitsNegative.isEmpty()){
			units.add(unitsNegative);
		}
		
		return units;
	}
	
	
	/**
	 * @param x
	 * @param y
	 * @param switchType
	 * @return
	 */
	private EliminateUnits searchForEliminateSingleUnit(int x, int y, int switchType) {
		EliminateUnits eliminateUnits = null;
		
		int unitType = -1;
		switch (switchType) {
		case SWITCH_LEFT:
			if (x - 1 >= 0) {
				unitType = unitMatrix[x - 1][y];
			}
			break;
		case SWITCH_RIGHT:
			if (x + 1 < width) {
				unitType = unitMatrix[x + 1][y];
			}
			break;
		case SWITCH_UP:
			if (y - 1 >= 0) {
				unitType = unitMatrix[x][y - 1];
			}
			break;
		case SWITCH_DOWN:
			if (y + 1 < height) {
				unitType = unitMatrix[x][y + 1];
			}
			break;
		}

		if (unitType != -1) {
			eliminateUnits = searchEliminateDirection(x, y, unitType, switchType);
		}
		return eliminateUnits;
	}
	
	
/**
 * @param x
 * @param y
 * @param unitType
 * @param switchType
 * @return
 */
	private EliminateUnits searchEliminateDirection(int x, int y, int unitType,
			int switchType) {
		int left = 0;
		int right = 0;
		int up = 0;
		int down = 0;

		int sameNumHor = 1;
		int sameNumVer = 1;

		boolean eliminateSelf = false;
		
		EliminateUnits eliminateUnits = new EliminateUnits(unitType);
		if (switchType == SWITCH_LEFT || switchType == SWITCH_RIGHT){
			if (switchType == SWITCH_LEFT){
				while ((x + right + 1) < width
						&& unitMatrix[x + right + 1][y] == unitType) {
					right++;
				}
				sameNumHor += right;
			}else if (switchType == SWITCH_RIGHT){
				while (x - (left + 1) >= 0
						&& unitMatrix[x - (left + 1)][y] == unitType) {
					left++;
				}
				sameNumHor += left;
			}
			
			while ((y - (up + 1)) >= 0
					&& unitMatrix[x][y - (up + 1)] == unitType) {
				up++;
			}
			sameNumVer += up;

			while ((y + down + 1) < height && unitMatrix[x][y + down + 1] == unitType) {
				down++;
			}
			sameNumVer += down;

		}else if (switchType == SWITCH_UP || switchType == SWITCH_DOWN){
			if (switchType == SWITCH_UP){
				while ((y + down + 1) < height && unitMatrix[x][y + down + 1] == unitType) {
					down++;
				}
				sameNumVer += down;
			}else if (switchType == SWITCH_DOWN){
				while ((y - (up + 1)) >= 0
						&& unitMatrix[x][y - (up + 1)] == unitType) {
					up++;
				}
				sameNumVer += up;
			}
			
			while (x - (left + 1) >= 0
					&& unitMatrix[x - (left + 1)][y] == unitType) {
				left++;
			}
			sameNumHor += left;

			while ((x + right + 1) < width
					&& unitMatrix[x + right + 1][y] == unitType) {
				right++;
			}
			sameNumHor += right;
		}
		
		if (sameNumHor >= eliminateNum) {
			eliminateSelf = true;
			
			for (int i = 1; i <= left; i++){
				eliminateUnits.add(new UnitPosition(x - i, y));
			}
			for (int i = 1; i <= right; i++){
				eliminateUnits.add(new UnitPosition(x + i, y));
			}
		}

		if (sameNumVer >= eliminateNum) {
			eliminateSelf = true;
			
			for (int i = 1; i <= up; i++){
				eliminateUnits.add(new UnitPosition(x, y - i));
			}
			for (int i = 1; i <= down; i++){
				eliminateUnits.add(new UnitPosition(x, y + i));
			}
		}
		
		if (eliminateSelf == true){
			eliminateUnits.add(new UnitPosition(x, y));
		}

		return eliminateUnits;
	}

	public String getSuggestionListStr() {
		StringBuffer strBuf = new StringBuffer();
		for (int i = 0; i < suggestionList.size(); i++) {
			Suggestion sug = suggestionList.get(i);
			strBuf.append(sug.toString() + "; ");
		}
		return strBuf.toString();
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				sb.append(unitMatrix[x][y] + ", ");
			}
			sb.append("\n");
		}
		return sb.toString();
	}

	public String getMaskString(){
		StringBuffer sb = new StringBuffer();
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				sb.append(maskMatrix[x][y] + ", ");
			}
			sb.append("\n");
		}
		return sb.toString();
	}
	
	public String getMaskStr() {
		StringBuffer sb = new StringBuffer();
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				sb.append(maskMatrix[x][y] + ", ");
			}
			sb.append("\n");
		}
		return sb.toString();
	}
	
	public static void main(String[] args) {
		MainMatrix matrix = new MainMatrix(10, 10, 5, 3);
		matrix.generateInitMatrix();
		// System.out.println(matrix.toString());
		// System.out.println(matrix.getMaskStr());

		matrix.getAllSuggestions();
		System.out.println(matrix.getSuggestionListStr());
	}
}

class EliminateCluster {
	public static final int TYPE_X = 0;
	public static final int TYPE_Y = 1;

	int startX;
	int startY;
	int destoryType;
	int number;
	int unitType;

	public EliminateCluster(int startX, int startY, int destoryType,
			int number, int unitType) {
		this.startX = startX;
		this.startY = startY;
		this.destoryType = destoryType;
		this.number = number;
		this.unitType = unitType;
	}
}

class EliminateUnits {
	public int unitType;
	public List<UnitPosition> posList = new ArrayList<UnitPosition>();
	
	public EliminateUnits(int unitType){
		this.unitType = unitType;
	}
	
	public void add(UnitPosition pos){
		posList.add(pos);
	}
	
	public boolean isEmpty(){
		return posList.size() == 0;
	}
}

class Suggestion {
	public int x;
	public int y;
	public int switchType;

	public Suggestion(int x, int y, int switchType){
		this.x = x;
		this.y = y;
		this.switchType = switchType;
	}
	
	EliminateUnits firstEliminateUnits;
	EliminateUnits secondEliminateUnits;
	
}
